package com.cn.algorithm01;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/22 20:15
 * 将多个单链结构拼接成按照顺序的一个长链，通过小根堆实现
 * isEmpty()  和   null的关系
 *
 */
public class Code16_MergeKSortedLists {
    // 单链表结构
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        map = null;
        System.out.println(map == null);
        System.out.println(map.isEmpty());

    }

    // 比较器
    public static class ListNodeComparator implements Comparator<ListNode> {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

    // 核心算法：通过小根堆PriorityQueue对数据进行排序
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }

        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new ListNodeComparator());
        for (ListNode node : lists) {
            if (node != null) {
                heap.add(node);
            }
        }

        if (heap.isEmpty()) {
            return null;
        }

        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }

        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;

            if (cur.next != null) {
                heap.add(cur.next);
            }

        }

        return head;

    }

}
